package 数据结构.链表.非带头链表.循环链表.单向链表;

import 数据结构.链表.IList;

public class MyLinkedList implements IList {
    static class ListNode{
        private int value;
        private ListNode next;
        public ListNode(int value){
            this.value = value;
        }
    }
    ListNode Head;
    ListNode Last;
    public MyLinkedList(){
        Head = null;
        Last = null;
    }

    @Override
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        if(Head == null){
            Head = newNode;
            newNode.next = Head;
            Last = newNode;
        }else{
            newNode.next = Head;
            Head = newNode;
            Last.next = Head;//不加出错
        }
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        if(Last == null){
            addFirst(data);
        } else {
            Last.next = newNode;
            newNode.next = Head;
            Last = newNode;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        if(index <= 1 ){
            addFirst(data);
            return;
        }
        if(index >= size()){
            addLast(data);
            return;
        }
        ListNode newNode = new ListNode(data);
        ListNode cur = Head.next;
        ListNode prev = Head;
        int count=1;
        while(cur != Head){
            count++;
            if(count == index){
                prev.next = newNode;
                newNode.next = cur;
                return;
            }
            cur = cur.next;
            prev = prev.next;
        };

    }

    @Override
    public boolean contains(int key) {
        ListNode cur = Head;
        do{
            if(cur.value == key){
                return true;
            }
            cur = cur.next;
        }while(cur != Head);
        return false;
    }

    @Override
    public void remove(int key) {
        if(Head.value == key){
            Head = Head.next;
            Last.next = Head;
            return;
        }
        ListNode cur = Head.next;
        ListNode prev = Head;
        while(cur != Head){
            if(cur.value == key){
                prev.next = cur.next;
                return;
            }
            cur = cur.next;
            prev = prev.next;
        }
    }

    @Override
    public void removeAllKey(int key) {
        while(Head.value == key){
            Head = Head.next;
            Last = Head;
        }
        ListNode cur = Head.next;
        ListNode prev = Head;
        while(cur != Head){
            if(cur.value == key){
                prev.next = cur.next;
                cur = prev.next;
                continue;
            }
            cur = cur.next;
            prev = prev.next;
        }
    }

    @Override
    public int size() {
        ListNode cur = Head;
        if(cur == null){
            return 0;
        }
        int size = 0;
        do{
            size++;
            cur = cur.next;
        }while(cur != Head);
        return size;
    }

    @Override
    public void clear() {
        Head = null;
    }

    @Override
    public void display() {
        if(Head == null){
            System.out.println("链表为空");
            return;
        }
        ListNode cur = Head;
        do{
            System.out.print(cur.value + " ");
            cur = cur.next;
        }while(cur != Head);
        System.out.println();
    }
}
